package offer_test_20;

import java.util.Arrays;

import struct.BinaryTree;
import struct.BinaryTreeNode;

;
//输入二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设前序遍历和中序遍历结果中都不包含重复的数字，
//例如输入的前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}重建出如图所示的二叉树。

public class six_BinaryTreeRebuilt {
	public static void main(String[] args) throws Exception {
		int[] inorder = { 4, 7, 2, 1, 5, 3, 8, 6 };
		int[] preorder = { 1, 2, 4, 7, 3, 5, 6, 8 };
//		System.out.println(Arrays.toString(Arrays.copyOfRange(inorder, 3,
//				inorder.length)));
		BinaryTreeNode btree = rebuilt(inorder, preorder);
		BinaryTree.printInorder(btree);
	}

	public static BinaryTreeNode rebuilt(int[] inorder, int[] preorder)
			throws Exception {
		if (preorder == null || inorder == null) {
			return null;
		}
		if (preorder.length == 0 || inorder.length == 0) {
			return null;
		}
		if (preorder.length != inorder.length) {
			throw new Exception("长度不一样，非法的输入");
		}
		BinaryTreeNode root = new BinaryTreeNode();
		root.value=preorder[0];
		int num = findinarray(inorder, preorder[0]);

		root.leftNode = rebuilt(Arrays.copyOfRange(inorder, 0, num),
				Arrays.copyOfRange(preorder, 1, num + 1));
		root.rightNode = rebuilt(
				Arrays.copyOfRange(inorder, num + 1, inorder.length),
				Arrays.copyOfRange(preorder, num + 1, preorder.length));
		return root;
	}

	public static int findinarray(int[] array, int num) {
		for (int i = 0; i < array.length; i++) {
			if (array[i] == num) {
				return i;
			}
		}
		return -1;
	}

}
